#include <stdio.h>
#include <stdlib.h>

/*
 * 线性探查
 */

/*
  一：散列表创建方法
  A.直接定址
  B.数字分析
  C.平方取中
  D.折叠
  E.除留余数法

  二:解决冲突办法
  A.开放定址
     1.线性探查
     2.平方探查
     3.双散列函数探查
    
  B.链址法

 */

#define HASH_LEN 13
#define TABLE_LEN 8

int hash_data[] = {18, 75, 60, 43, 54, 90, 46};
int des[13] = {0};

void insert_hash(int * hash, int len, int data)
{
  int i;

  i = data % 13;  // 计算哈希地址
  while (hash[i])  // 元素位置已被占用
    i = (++i) % len;  // 线性探测法解决冲突。（即找下一个空位）
  hash[i] = data;
}

void createhash(int hash[], int m, int src[], int len)
{
  int i;

  for (i = 0; i < len; i++)
    insert_hash(hash, m, src[i]);
}

int search(int hash[], int m, int key)
{
  int i;

  i = key % 13;
  while (hash[i] && hash[i] != key) // 判断是否冲突
    i = (++i) % m;  // 线性探测法解决冲突
  if (hash[i] == 0) // 查找到开放单元，表示查找失败
    return -1;
  else
    return i;
}

int main()
{
  int key, i, pos;

  createhash(des, HASH_LEN, hash_data, TABLE_LEN);

  for (i = 0; i < HASH_LEN; i++)
    printf(" %d ", des[i]);
  printf("\n");

  printf("input find key:");
  scanf("%d", &key);

  pos = search(des, HASH_LEN, key);
  if (pos > 0)
    printf("find successfuly, the key is %d position.\n", pos);
  else
    printf("find fial.\n");
}




